from LeetTool import TreeNode
from LeetTool import build_TreeNode


class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right


if __name__ == "__main__":
    print(Solution().kthSmallest(build_TreeNode([3, 1, 4, None, 2]), 1))  # 1
    print(Solution().kthSmallest(build_TreeNode([5, 3, 6, 2, 4, None, None, 1]), 3))  # 3
